import java.util.*;
//力扣394. 字符串解码
class Solution {
    public String decodeString(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)!=']'){
                //不是'['入栈
                stack.push(s.charAt(i));
            }else{
                //一旦遇到']'就新建一个字符串s1存储当前'[]'内的字符
                StringBuilder s1=new StringBuilder();
                //遇到'['停止
                while(stack.peek()!='['){
                    s1.append(stack.pop());
                }
                //去掉'['
                stack.pop();
                //num记录重复的次数,flag记录位数(重复的次数范围是1~300)
                int num=0;
                int flag=0;
                //计算重复的次数,注意判空
                while(!stack.isEmpty()&&stack.peek()-'0'>=0&&stack.peek()-'0'<=9){
                    num=(stack.pop()-'0')*(int)Math.pow(10,flag)+num;
                    flag++;
                }
                //根据重复的次数将s1入栈，注意s1是倒着的字符串，所以从末尾遍历
                for(int j=0;j<num;j++){
                    for(int k=s1.length()-1;k>=0;k--){
                        stack.push(s1.charAt(k));
                    }
                }
            }
        }
        //最终结果
        StringBuilder res=new StringBuilder();
        while(!stack.isEmpty()){
            res.append(stack.pop());
        }
        //翻转
        return res.reverse().toString();
    }
}




//43. 字符串相乘
class Solution1 {
    public String multiply(String num1, String num2) {
        int len1=num1.length();
        int len2=num2.length();
        //长度设置为len1+len2避免9*9=81的情况
        int[] arr=new int[len1+len2];
        int flag=0;
        for(int i=len1-1;i>=0;i--){
            flag=i+len2;
            for(int j=len2-1;j>=0;j--){
                int num=(num1.charAt(i)-'0')*(num2.charAt(j)-'0');
                int carry=num/10;
                int cur=num%10;
                arr[flag]+=cur;
                //如果当前位大于10了就进位
                if(arr[flag]>=10){
                    //确保当前位-1还是有效位
                    //然后进位
                    if(flag-1>=0){
                        arr[flag-1]+=arr[flag]/10;
                        arr[flag]=arr[flag]%10;
                    }
                }
                //进位
                if(flag-1>=0){
                    arr[flag-1]+=carry;
                }
                flag--;
            }
        }
        StringBuffer res=new StringBuffer();
        for(int i=0;i<arr.length;i++){
            //把前边为零的消掉(比如2*3 arr数组存储的是0 6),同时避免了一些长数组相乘为零的情况
            //(比如0*9901 arr数组存储为0 0 0 0 0。)
            if(!(res.length()==0&&arr[i]==0)){
                res.append(arr[i]);
            }
        }
        //如果res.length==0说明结果为0
        return res.length()==0?"0":res.toString();
    }
}